Nils:

	I just got  a memo by  Fuller, Gaschnig, and  Gillogly called
"analysis of the alpha-beta pruning algorithm" from Carngegie-Mellon.
At first sight, there isn't much new  in it, but anyway it led me  to
look  in  your  book  where   you  discuss  the  history,    somewhat
incorrectly.   The history is complicated by  the fact that those who
devised it didn't make much of it.  Anyway here is what I know.

	I  first thought  of  it  at the  Dartmouth  Summer  Research
Project  on Artificial Intelligence  in 1956 when  Bernstein proposed
his chess program.  As you may  know this program branched 7 ways  at
each level according to priority criteria, but didn't use any form of
alpha-beta. I  criticized it on the spot  for this, but Bernstein was
not convinced. No formal specification of the algorithm was  given at
that time. Later, when I worked on the chess routines that were later
taken  over by  Kotok,   I had  Paul Abrahams  write a two  move mate
program which (I believe)  used alpha-beta.  The term  alpha-beta was
introduced  by me when  I wrote a  LISP version.   However,   my LISP
program was more elaborate than simple alpha-beta in that it used  an
optimistic  and pessimistic  evaluation  of  positions, and  I  never
realized  that  the  simple version  gave  the  same  answer as  full
minimax.  This came out when I criticized a kalah program written for
the PDP-1 by  Roland Silver, because it used full  minimax.  The fact
that  alpha-beta gave the  same result as minimax  was discovered and
proved by Edwards and Hart.

	The kalah program you refer to was written by  Edwards at MIT
under my direction, and was only slightly modified by Richard Russell
at Stanford when I  moved to Stanford.   The Kotok chess program  was
based on my routines and was written by Kotok, Niessen, and one other
as bachelor's thesis work  supervised by me.  As you say, it was only
slightly modified when taken to Stanford.

	It was never clear to me whether the early Newell-Simon chess
programs  contained  alpha-beta  or  not.     It  certainly  was  not
disentangled  by them  from other  features of  chess programs.   The
Russian  use  of alpha-beta  was  certainly  independent,    and  the
algorithm  was desribed in  a paper  by Brudno about  1963 a  copy of
which I had but  seem to have  mislaid.  I  believe it was  described
entirely abstractly  rather than  in connection  with an actual  game
program.

	All   the  MIT   uses  of  alpha-beta   were  based   on  the
understanding that  the  full advantage  of  the algorithm  would  be
obtained only in  connection with a move-orderer that  tried the most
likely moves first.

	The  main contribution of Richard Russell  was to make a long
series of experiments with the kalah program that  showed the effects
of  different  settings of  the  parameters and  also  the series  of
computer runs that showed that the  3-in-a-pit game is a win for  the
first  player.  This   also  showed  the  need  for   an  "impatience
heuristic".    Unfortunately,  the limitations  of  the  PDP-1 memory
prevented interesting extensions, and the results were never properly
written up.

	The original  alpha-beta formalization  was approximately  as
follows:

	valmax[p,alpha,beta] ← if optimistic p ≤ alpha then alpha
else if pessimistic p > beta then beta
else if ter p then imval p
else valmaxlis[successors p,alpha,beta]

	valmaxlis[u,alpha,beta] ← if null u then alpha
else [lambda x. if x ≤ alpha then valmaxlis[cdr u,alpha, beta]
		else if x ≥ beta then beta
		else valmaxlis[cdr u,x,beta]]
	[valmin[car u,alpha,beta]]

with valmin  and  valminlis defined  analogously.   Edwards and  Hart
removed  the optimistic  and pessimistic  evaluations, and  I suppose
they are  correct  in  saying  that Mike  Levin  proved  the  theorem
although I don't remember it.

	The  above  LISP formulation  was  never  used as  an  actual
program,  because  the programs  for  chess  and kalah  were  done in
Fortran and PDP-1 assembly language respectively.

	Well, I suppose  this doesn't differ  too much from  what you
say in your book.